/*
 * Sudoku.c
 *
 *  Created on: 20 oct. 2011
 *      Author: alex
 */
#include <stdio.h>
#include <stdlib.h>
#include "Sudoku.h"

Sudoku_s* creer_sudoku_std( void ){
	Sudoku_s* s = creer_sudoku( 9, 9);
	return s;
}

Sudoku_s* creer_sudoku( const int hauteur, const int largeur ){
	Sudoku_s* s = (Sudoku_s*) malloc( sizeof( Sudoku_s ));
	int i,j;

	s->hauteur = hauteur;
	s->largeur = largeur;
	s->tab = (int**) malloc( sizeof( int* ) * s->hauteur);
	for( i = 0; i < s->hauteur; i++ ){
		s->tab[i] = (int*) malloc( sizeof( int ) * s->largeur );
		for( j = 0; j < s->largeur; j++){
			s->tab[i][j] = 0;
		}
	}

	return s;
}

void nouvelle_ligne( Sudoku_s *sudoku, const int ligne ){
	int hazard;
	int valeurs[9];
	int i,cpt;

	for( i = 0; i < 9; i++ ){
		valeurs[i] = 0;
	}
	for( i = 0; i < 9; i++ ){
		cpt = 0;
		do{
			hazard = (random()%9);
			cpt++;
		}while( cpt < 39 && (valeurs[hazard] || present_dans_carre( sudoku, i, ligne, hazard+1) || present_dans_colonne(sudoku, i, hazard+1) || present_dans_ligne(sudoku, ligne, hazard+1)));
		if( cpt == 39 ){
			fprintf(stderr,"Pas reussi à trouver!\n");
			return;
		}
		sudoku->tab[ligne][i] = hazard+1;
		valeurs[hazard] = 1;
	}
}

void construit_grille( Sudoku_s *sudoku ){
	int i,cpt = 1;

	for( i = 1; i < 10; i++ ){
		if( place_number( sudoku, i) == 0 ){
			cpt++;
			vide_grille( sudoku );
			i = 0;
		}

	}
#ifdef DEBUG
	printf("Il y a eu %d tentatives\n",cpt);
#endif
}

void construit_grille2( Sudoku_s *sudoku ){
	int i,cpt = 1, limite;

	limite = 0;
	for( i = 1; i < 10; i++ ){
		printf("Placement de %d\n",i);
		while( place_number( sudoku, i) == 0 && limite < 30){
			printf("Suppresssion de %d\n",i);
			vide_grille_number( sudoku, i );
			cpt++;
			limite++;
		}
		if( limite == 30 ) {
			printf("Suppresssion de %d\n",i);
			vide_grille_number( sudoku, i );
			i--;
			if( i < 1 )
				i = 1;
			printf("Suppresssion de %d\n",i);
			vide_grille_number( sudoku,  i );
		}
		if( limite > 100 ){
			vide_grille( sudoku );
			i = 1;
			limite = 0;
		}

	}
#ifdef DEBUG
	printf("Il y a eu %d tentatives\n",cpt);
#endif
}

void construit_grille3( Sudoku_s const *sudoku ){
	int cpt = 0, test;
	
	do{
		cpt++;
		test = place_numero( sudoku, 1);
		
	}while( cpt < 10 && !test );
	if( cpt >= 10 ){
		fprintf(stderr, "Erreur, Grille valide non trouvee!\n");
		exit( EXIT_FAILURE );
	}
}

int place_numero( Sudoku_s *sudoku, int number ){
	int i, max = 20,j;
	
	// Je fait max tentatives pour placer le nombre "number" dans la grille
	for( i = 0; i <= max; i++ ){
		//pour chaque tentative, si j'ai reussi à placer le numero
#ifdef DEBUG
		for( j = 0; j < number; j++ ){
			printf("     ");
		}
		printf("Placement de %d...",number);
#endif
		if( place_number( sudoku, number) == 1 ){
#ifdef DEBUG
			printf("OK!\n");
#endif
			//si il s'agissait du numero 9 c'est terminé
			if( number == 9 )
				return 1;
			else{
				//si c'est pas le 9, il faut placer le suivant, si c'est reussi on continue, sinon on change le numero
				if( place_numero( sudoku, number+1) == 1 ){
					return 1;
				}else
					vide_grille_number(sudoku, number+1);
			}
		}else{
#ifdef DEBUG
			printf("FAIL!\n");
#endif
			vide_grille_number( sudoku, number);
		}
	}
	return 0;
}

void vide_grille_number( Sudoku_s *sudoku, const int number ){
	int i,j;

	for( i = 0; i < 9; i++ ){
		for( j = 0; j < 9; j++ ){
			if( sudoku->tab[i][j] == number )
				sudoku->tab[i][j] = 0;
		}
	}
}

Sudoku_s* copy_sudoku( const Sudoku_s const * sudoku){
	Sudoku_s *s = creer_sudoku( sudoku->hauteur, sudoku->largeur );
	int i,j;

	for( i = 0; i < sudoku->hauteur; i++ ){
		for( j = 0; j < sudoku->largeur; j++ ){
			s->tab[i][j] = sudoku->tab[i][j];
		}
	}

	return s;
}

char demande_lettre( void ){
	char c;
	fread(&c, sizeof( char ), 1, stdin);
	return c;
}

void vide_grille( Sudoku_s *sudoku ){
	int i,j;

	for( i = 0; i < 9; i++ ){
		for( j = 0; j < 9; j++ ){
			sudoku->tab[i][j] = 0;
		}
	}
}

int supprime_case( Sudoku_s *sudoku ){
	int ss_ligne, ss_colonne;
	int carre_ligne = random()%3;
	int carre_colonne = random()%3;
	int x,y,recherche;
	int i,j;

	do{
		ss_ligne = random()%3;
		ss_colonne = random()%3;

		x = ss_colonne+3*carre_colonne;
		y = ss_ligne + 3 * carre_ligne;
		recherche = sudoku->tab[y][x];

		//si on obtient une case vide, on cherche une case non vide
		if( recherche == 0 ){

			i = x;
			do{
				i++;
			}while( i < 9 && sudoku->tab[y][i] == 0 );

			if( i >= 9 ){
				j = y;

				do{
					j++;
				}while( j < 9 && sudoku->tab[j][x] == 0);
				if( j < 9 )
					y = j;
			}else{
				x = i;
			}
			ss_colonne = x%3;
			carre_colonne = x/3;
			ss_ligne = y%3;
			carre_ligne = y/3;
		}

	}while( sudoku->tab[y][x] == 0 );

	switch( ss_ligne ){
	case 0:
		if( present_dans_ligne( sudoku, y+1, recherche) && present_dans_ligne( sudoku, y+2, recherche) ){
			switch( ss_colonne ){
				case 0:
					if( present_dans_colonne( sudoku, x+1, recherche) && present_dans_colonne( sudoku, x+2, recherche) ){
						sudoku->tab[y][x] = 0;
						return 1;
					}
					break;
				case 1:
					if( present_dans_colonne( sudoku, x-1, recherche) && present_dans_colonne( sudoku, x+1, recherche) ){
						sudoku->tab[y][x] = 0;
						return 1;
					}
					break;
				case 2:
					if( present_dans_colonne( sudoku, x-1, recherche) && present_dans_colonne( sudoku, x-2, recherche) ){
						sudoku->tab[y][x] = 0;
						return 1;
					}
					break;
				default:
					fprintf(stderr, "Erreur! Sous possibilitee non prevu dans la suppression de case\n");
			}
		}
		break;
	case 1:
		if( present_dans_ligne( sudoku, y-1, recherche) && present_dans_ligne( sudoku, y+1, recherche) ){
			switch( ss_colonne ){
				case 0:
					if( present_dans_colonne( sudoku, x+1, recherche) && present_dans_colonne( sudoku, x+2, recherche) ){
						sudoku->tab[y][x] = 0;
						return 1;
					}
					break;
				case 1:
					if( present_dans_colonne( sudoku, x-1, recherche) && present_dans_colonne( sudoku, x+1, recherche) ){
						sudoku->tab[y][x] = 0;
						return 1;
					}
					break;
				case 2:
					if( present_dans_colonne( sudoku, x-1, recherche) && present_dans_colonne( sudoku, x-2, recherche) ){
						sudoku->tab[y][x] = 0;
						return 1;
					}
					break;
				default:
					fprintf(stderr, "Erreur! Sous possibilitee non prevu dans la suppression de case\n");
			}
		}
		break;
	case 2:
		if( present_dans_ligne( sudoku, y-1, recherche) && present_dans_ligne( sudoku, y-2, recherche) ){
			switch( ss_colonne ){
				case 0:
					if( present_dans_colonne( sudoku, x+1, recherche) && present_dans_colonne( sudoku, x+2, recherche) ){
						sudoku->tab[y][x] = 0;
						return 1;
					}
					break;
				case 1:
					if( present_dans_colonne( sudoku, x-1, recherche) && present_dans_colonne( sudoku, x+1, recherche) ){
						sudoku->tab[y][x] = 0;
						return 1;
					}
					break;
				case 2:
					if( present_dans_colonne( sudoku, x-1, recherche) && present_dans_colonne( sudoku, x-2, recherche) ){
						sudoku->tab[y][x] = 0;
						return 1;
					}
					break;
				default:
					fprintf(stderr, "Erreur! Sous possibilitee non prevu dans la suppression de case\n");
			}
		}
		break;
	default:
		fprintf(stderr, "Erreur! Possibilitee non prevu dans la suppression de case\n");
		break;
	}
	return 0;
}

void troue_grille( Sudoku_s *sudoku ){
	int i;
	int max = (random()%5)+30;
	int cpt;

#ifdef DEBUG
	printf("Suppression de %d cases\n",max);
#endif

	for( i = 0; i < max; i++ ){
		cpt= 0;
		while( cpt < 30 && supprime_case( sudoku ) == 0){
			cpt++;
		}

		if( cpt >= 30 ){
			fprintf(stderr, "Impossible de trouver une %deme suppression\n",i);
		}
	}
}

int place_number( Sudoku_s *sudoku, const int number ){
	// Coordonnees ou va etre place le nombre
	int x,y;
	int i,j,cpt;
	for( i = 0; i < 3; i++ ){
		for( j = 0; j < 3; j++ ){
			cpt = 0;
			do{
				cpt++;
				x = (random()%3)+(3*i);
				y = (random()%3)+(3*j);
				if( cpt == 15 )
					return 0;
				

			}while( sudoku->tab[y][x] || present_dans_colonne( sudoku, x, number) || present_dans_ligne( sudoku, y, number));

			sudoku->tab[y][x] = number;
		}
	}
	return 1;
}

int present_dans_colonne( const Sudoku_s const *sudoku, const int colonne, const int recherche ){
	int i;

	for( i = 0; i < sudoku->hauteur; i++ ){
		if( sudoku->tab[i][colonne] == recherche )
			return 1;
	}

	return 0;
}

int present_dans_ligne( const Sudoku_s const *sudoku, const int ligne, const int recherche ){
	int i;

	for( i = 0; i < sudoku->largeur; i++ ){
		if( sudoku->tab[ligne][i] == recherche )
			return 1;
	}

	return 0;
}

int present_dans_carre( const Sudoku_s const *sudoku, const int colonne, const int ligne, const int recherche ){
	int i,j;

	if( colonne < 3 ){
		if( ligne < 3 ){
			for( i = 0; i < 3; i++ ){
				for( j = 0; j < 3; j++ ){
					if( sudoku->tab[i][j] == recherche )
						return 1;
				}
			}
		}else if( ligne < 6 ){
			for( i = 3; i < 6; i++ ){
				for( j = 0; j < 3; j++ ){
					if( sudoku->tab[i][j] == recherche )
						return 1;
				}
			}
		}else{
			for( i = 6; i < 9; i++ ){
				for( j = 0; j < 3; j++ ){
					if( sudoku->tab[i][j] == recherche )
						return 1;
				}
			}

		}
	}else if( colonne < 6 ){
		if( ligne < 3 ){
			for( i = 0; i < 3; i++ ){
				for( j = 3; j < 6; j++ ){
					if( sudoku->tab[i][j] == recherche )
						return 1;
				}
			}

		}else if( ligne < 6 ){
			for( i = 3; i < 6; i++ ){
				for( j = 3; j < 6; j++ ){
					if( sudoku->tab[i][j] == recherche )
						return 1;
				}
			}
		}else{
			for( i = 6; i < 9; i++ ){
				for( j = 3; j < 6; j++ ){
					if( sudoku->tab[i][j] == recherche )
						return 1;
				}
			}
		}
	}else{
		if( ligne < 3 ){
			for( i = 0; i < 3; i++ ){
				for( j = 6; j < 9; j++ ){
					if( sudoku->tab[i][j] == recherche )
						return 1;
				}
			}
		}else if( ligne < 6 ){
			for( i = 3; i < 6; i++ ){
				for( j = 6; j < 9; j++ ){
					if( sudoku->tab[i][j] == recherche )
						return 1;
				}
			}
		}else{
			for( i = 6; i < 9; i++ ){
				for( j = 6; j < 9; j++ ){
					if( sudoku->tab[i][j] == recherche )
						return 1;
				}
			}
		}
	}
	return 0;
}

void libere_sudoku( Sudoku_s **sudoku ){
	int i;

	for( i = 0; i < (*sudoku)->hauteur; i++ ){
		free( (*sudoku)->tab[i] );
	}
	free( (*sudoku)->tab );
	free( *sudoku );
	*sudoku = NULL;
}

void print_Sudoku( const Sudoku_s const * sudoku){
	int i,j;

	printf("    1 2 3   4 5 6   7 8 9\n");
	for( i = 0; i < sudoku->hauteur; i++ ){
		if( i%3 == 0 )
			printf("\n");
		printf("%d ",i+1);
		for( j = 0; j < sudoku->largeur; j++ ){
			if( j%3 == 0 )
				printf(" |");
			if( !sudoku->tab[i][j] )
				printf(" |");
			else
				printf("%d|",sudoku->tab[i][j]);
		}
		printf("\n");
	}
}
